package LInkedList;

import java.util.NoSuchElementException;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:岁亮亮
 * Date:2024-05-20
 * TIME:15:52
 */
public class MySingleList implements MyList{



    private static class ListNode{
        int value;
        ListNode next;   //next域 指向下一个节点 的地址
        public ListNode(int value){  //因为不知道下一个节点是谁 不能传next
            this.value = value;
        }
    }
    private ListNode head;
    public MySingleList(){

    }

    @Override
    public boolean add(int data) {
        addLast(data);
        return true;
    }

    @Override
    public void addFirst(int data) {
       ListNode cur = new ListNode(data);
       if(head == null){
           this.head = cur;
       }
       else {
           cur.next = this.head;
           head = cur;
       }


    }

    @Override
    public void addLast(int data) {
        ListNode cur = this.head;
        ListNode end = new ListNode(data);
        if(cur == null){
            this.head = end;
            return;
        }
        while (cur.next != null){
            cur = cur.next;
        }
        cur.next = end;


    }

    @Override
    public int removeLast() {
        return 0;
    }

    @Override
    public void addIndex(int index, int data) {
        checkPositionIndex(index);
        //assert 检查完下标之后 链表若为空 那么在不抛出异常前提下index 只能为0
        if(index == 0){
            addFirst(data);
            return;
        }
        ListNode current = this.head;
        ListNode addNode = new ListNode(data);

        for (int i = 0; i < index - 1; i++) {
            current = current.next;
        }
        ListNode preNode = current.next;
        current.next = addNode;
        addNode.next = preNode;

    }
    //在倒数第index 下标添加元素
    public void addIndexResrvate(int index, int data){
        checkPositionIndex(index);
       addIndex(this.size()-index,data);
    }

    private void checkPositionIndex(int index) {
        if(index < 0 || index > this.size()){
            throw new IllegalArgumentException();
        }
    }

    @Override
    public int indexOf(int key) {
        ListNode cur = this.head;
        if(cur == null){
            throw new NoSuchElementException();
        }
        int count = 0;
        while (cur != null){
            if(cur.value == key){
                return count;
            }
            count++;
            cur = cur.next;
        }
        return -1;
    }

    @Override
    public boolean contains(int key) {
       return indexOf(key) >=0;
    }
    @Override
    public int removeFirst() {
        ListNode cur = this.head;
        if(cur == null){
            throw new NoSuchElementException();
        }
        int value = cur.value;
        this.head = null;
        cur = cur.next;
        this.head = cur;
        return value;
    }


    @Override
    public void remove(int key) {
        ListNode cur = this.head;
        if(cur == null){
            throw new NoSuchElementException();
        }
        int count = 0;
        while (cur != null){
            if(cur.value == key){
                removeIndex(count);
                return;
            }
            count++;
            cur = cur.next;
        }

    }
    @Override
    public int removeIndex(int index) {
        checkElementIndex(index);
       ListNode cur = this.head;
        if(index == 0){
            return removeFirst();
        }
        for (int i = 0; i < index - 1; i++) {
            cur = cur.next;
        }

        ListNode midNode = cur.next;
        int value = midNode.value;
        cur.next = midNode.next;
        midNode = null;
        return value;
    }
    public int removeIndexResrvate1(int index){
        checkElementIndex(index);
        if(this.head == null){
            throw new NoSuchElementException();
        }
        return removeIndex(this.size()-index-1);
    }
    public int removeIndexResrvate2(int index){
        checkElementIndex(index);
        ListNode cur = this.head;
        if(cur == null){
            throw new NoSuchElementException();
        }
        int count = index;
        while (cur != null){
           count--;
            cur = cur.next;
        }
        if(count == 0){
            cur = head;
           this.head = this.head.next;
           int value = cur.value;
            cur.value = -1;
            cur = null;
            return value;
        }
        else {
            cur = head;
            while (++count != 0){
                cur = cur.next;
            }
            ListNode mid = cur.next;
            cur.next = cur.next.next;
            int value = mid.value;
            mid.next = null;
            return value;
        }
    }

    /***
     * 找到倒数第 k 个节点
     * 1.有两个指针 都指向起始节点  倒数第 k 节点 要正走size - k 步
     * 2.首先让快指针 走 k-1 步到第k个节点 然后让快慢指针同时走  走到最后一个节点 快慢指针走的步数正好是size - k 步
     * 3.细节 首先判断 k 是否为负数 和头指针是否为空 然后判断快指针在走k-1步时是否为空
     * @param index
     * @return
     */
    public ListNode findIndexResrvate3(int index){//快慢指针的方法
        if(index <= 0 || head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        int count = 0;
        while ((index-1)!= count){
            fast = fast.next;
            if(fast == null){
                return null;
            }
            count++;
        }
        while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    private void checkElementIndex(int index) {
        if(index < 0 || index >=size()){
            throw new IndexOutOfBoundsException();
        }
    }

    @Override
    public void removeAllKey(int key) {
        ListNode cur = this.head;
        if(cur == null){
            throw new NoSuchElementException();
        }
        int count = 0;
        while (cur != null ){
            if(cur.value == key){
                removeIndex(count);
                count--;
            }
            count++;
            cur = cur.next;
        }
    }
    public void removeAllKey1(int key) {
        ListNode cur = this.head;
        if(cur == null){
            throw new NoSuchElementException();
        }
        ListNode pre = head;
        cur = cur.next;
        while (cur != null){
            if(cur.value == key){
                pre.next = cur.next;
                cur = cur.next;
            }
            else {
                pre = cur;
                cur = cur.next;
            }

        }
        if(head.value == key){
            head = head.next;

        }
    }

    public void reverseSingleList1(){
        if(this.head == null){
            return;
        }
        if(head.next == null){
            return;
        }
        ListNode Second = this.head.next;
        head.next = null;
        while (Second != null){
            ListNode mid = Second.next;
            Second.next = head;
            head = Second;
            Second = mid;
        }
    }

    public void reverseSingleList2(){
        ListNode pre = null;
        ListNode next = null;
        while (this.head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        this.head = pre;
    }

    public void reverseSingleListIndexOf(int from,int to){
        ListNode cur = this.head;
        while ((from-2) != 0){
            if(cur == null){
                return;
            }
            cur = cur.next;
            from--;
        }
        int count = to - from;
        if(count > 0){
            ListNode fromNode = cur.next;
            ListNode pre = cur;
            ListNode next = null;
            while (count != 0){
                next = fromNode.next;
                fromNode.next = pre;
                pre = fromNode;
                fromNode = next;
                count--;
            }
        }

    }
    @Override
    public int size() {
        int count = 0;
        ListNode cur = this.head;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
    public void createSingleList(){
        ListNode node1 = new ListNode(23);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(23);
        ListNode node4 = new ListNode(23);
        ListNode node5 = new ListNode(23);
           node1.next = node2;
           node2.next = node3;
           node3.next = node4;
           node4.next = node5;
           this.head = node1;
    }


    @Override
    public void clear() {
        ListNode cur = head;
        while (cur != null && cur.next != null){
            ListNode curNext = cur.next;
            cur.next = null;
            cur = curNext;
        }
        this.head = null;

    }

    @Override
    public void display() {
        ListNode cur = this.head;
        while (cur != null){
            System.out.println(cur.value);
            cur = cur.next;
        }

    }
    public ListNode middleList1(){
        ListNode cur = this.head;
        if(head == null || head.next == null){
            return head;
        }
        int usedSize = 0;
        while (cur != null){
            usedSize++;
            cur = cur.next;
        }
        int midIndex = usedSize/2;
        ListNode midPreNode = findNodeIndex(midIndex);
        midPreNode.next = midPreNode.next.next;
        return midPreNode;
    }

    private ListNode findNodeIndex(int midIndex) {
        ListNode cur = head;
        for (int i = 0; i < midIndex -1; i++) {
            cur = cur.next;
        }
        return cur;
    }


}
